# -*- coding: utf-8 -*-
# author yzs
# date 2018-12-17
#
# 倒置个数
# Description
# 有一个由N个实数构成的数组，如果一对元素A[i]和A[j]是倒序的，即i<j但是A[i]>A[j]则称它们是一个倒置，设计一个计算该数组中所有倒置数量的算法。要求算法复杂度为O(nlogn)
# Input
# 输入有多行，第一行整数T表示为测试用例个数，后面是T个测试用例，每一个用例包括两行，第一行的一个整数是元素个数，第二行为用空格隔开的数组值。
# Output
# 输出每一个用例的倒置个数，一行表示一个用例。
# Sample Input 1 
# 1
# 8
# 8 3 2 9 7 1 5 4
# Sample Output 1
# 17


def merge(left, right):
    array_before = left[0]
    mid_before = left[1]
    array_after = right[0]
    mid_after = right[1]
    mid = mid_before + mid_after
    flag = len(array_after) - 1
    array_merge = []
    for i in range(len(array_before) - 1, -1, -1):
        while array_before[i] <= array_after[flag] and flag >= 0:
            array_merge.append(array_after[flag])
            flag -= 1
        if flag == -1:
            break
        else:
            array_merge.append(array_before[i])
            mid += (flag + 1)
    if flag == -1:
        for j in range(i, -1, -1):
            array_merge.append(array_before[j])
    else:
        for j in range(flag, -1, -1):
            array_merge.append(array_after[j])
    return array_merge[::-1], mid


def merge_sort(array):
    if len(array) == 1:
        return (array, 0)
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    return merge(left, right)


T = int(input().strip())
for i in range(T):
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    A = A[:N]
    print(merge_sort(A)[1])
